#include <iostream>
#include <cstdlib>
#include <stdlib.h>
#include <vector> 
#include <time.h>
#define LENGTH 25

template <typename T>

class BinaryTree
{
private:
    class Node
    {
    public:
	T data;
	Node* lc;
	Node* rc;
	Node* parent;
	Node(T _data);
    };
    Node* root;
    void inorder_walk(Node* _x) const;
    void inorder_walk_test(Node* _x) const;
    void release(Node* _x);
    Node* successor(Node* _x) const;
    Node *predecessor(Node *_x) const;
    Node* min(Node* _x) const;
    Node *max(Node *_x) const;
public:
    BinaryTree() {root = NULL;};
    BinaryTree(T _data);
    ~BinaryTree();
    void insert(T _data);
    void inorder_walk() const;
    void inorder_walk_test() const;
    void test_successor();
    void test_predecessor();
    void tree_search(T _data);
    int transplant(Node *_u,Node *_v);
    int del(Node *_x);
    Node *getroot(); 
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::getroot()
{
	return root;
};
template <typename T>
void BinaryTree<T>::tree_search(T _data)
{
  Node *x=root;
  while(x != NULL)
    {
      if(x->data== _data)
	{
	  std::cout<<"it is in the array"<<std::endl;
	  break;
	}
      else if(x->data<_data)
	x=x->rc;
      else
	x=x->lc;
    }
  if(x==NULL)
    std::cout<<"can not be found"<<std::endl;
};
template <typename T>
void BinaryTree<T>::release(Node* _x)
{
    if (_x != NULL)
    {
	release(_x->lc);
	release(_x->rc);
	delete _x;
    }	
};

template <typename T>
BinaryTree<T>::~BinaryTree()
{
    release(root);
};

template <typename T>
BinaryTree<T>::Node::Node(T _data)
{
    data = _data;
    parent = lc = rc = NULL;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::successor(Node* _x) const
{
    Node* x = _x;
    if (x->rc != NULL)
	return min(x->rc);
    Node* y = x->parent;
    while (y != NULL && x == y->rc)
    {
	x = y;
	y = y->parent;
    }
    return y;
};

template <typename T>
void BinaryTree<T>::test_successor()
{
    std::cout << "successor: " << successor(root->lc->lc->rc)->data << std::endl;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::min(Node* _x) const
{
    while (_x->lc != NULL)
	_x = _x->lc;
    return _x;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::max(Node* _x) const
{
  while( _x->rc != NULL)
    _x = _x->rc;
  return _x;
};

template <typename T>
typename BinaryTree<T>::Node* BinaryTree<T>::predecessor(Node* _x) const
{
  Node *x=_x;
  if(x->lc != NULL)
    return max(x->lc);
  Node *y= x->parent;
  while (y != NULL && x == y->lc)
    {
	x = y;
	y = y->parent;
    }
    return y;

};

template <typename T>
void BinaryTree<T>::test_predecessor()
{
  std::cout<< "predecessor: "<< predecessor(root->rc)->data << std::endl;
};

template <typename T>
void BinaryTree<T>::inorder_walk() const
{
    inorder_walk(root);
    std::cout << std::endl;
};

template <typename T>
void BinaryTree<T>::inorder_walk(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk(_x->lc);
	std::cout << _x->data << "\t";
	inorder_walk(_x->rc);
    }
};

template <typename T>
void BinaryTree<T>::inorder_walk_test() const
{
    inorder_walk_test(root);
};

template <typename T>
void BinaryTree<T>::inorder_walk_test(Node* _x) const
{
    if (_x != NULL)
    {
	inorder_walk_test(_x->lc);
	inorder_walk_test(_x->rc);
    }
};

template <typename T>
void BinaryTree<T>::insert(T _data)
{
    Node* y = NULL;
    Node* x = root;
    Node* p = new Node(_data);
    while (x != NULL)
    {
	y = x;
	if (p->data  < x->data)
	    x = x->lc;
	else
	    x = x->rc;
    }
    p->parent = y;
    if (y == NULL)
	root = p;
    else if (p->data < y->data)
	y->lc = p;
    else
	y->rc = p;
};

template <typename T>
BinaryTree<T>::BinaryTree(T _data)
{
    Node* p = new Node(_data);
    if (root == NULL)
	root = p;
};

void RandomArray(std::vector<double>oldArray, std::vector<double>&newArray,int length) {
	for (int i = length; i > 0; i--)
	{
		srand(unsigned(time(NULL)));
		int index = rand() % i;
		newArray.push_back(oldArray[index]);
		oldArray.erase(oldArray.begin() + index);
	}
}

template <typename T>
int BinaryTree<T>::transplant(Node *_u, Node *_v)
{
	if (_u == NULL)
    {
        std::cerr << "Error! Can not transplant to a NULL."
                  << std::endl;
        std::exit(-1);
    }
    if (_u->parent == NULL)
        root = _v;                                                                     
    else if (_u == _u->parent->lc)
        _u->parent->lc = _v;
    else
        _u->parent->rc = _v;
    if (_v != NULL)                                                                                                          
    _v->parent = _u->parent;
    return 0;
};

template <typename T>
int BinaryTree<T>::del(Node *_x)
{
	if (_x->lc == NULL)
		this->transplant(_x, _x->rc);
  else if (_x->rc == NULL)
		this->transplant(_x, _x->lc);
  else
  {
		Node *y = min(_x->rc);
		if (y->parent != _x)   
		{
	  	this->transplant(y, y->rc);
	  	y->rc = _x->rc;
	  	y->rc->parent = y;
		}
		this->transplant(_x, y);
		y->lc = _x->lc;
		y->lc->parent = y;
  }
  delete _x;
  return 0;
};